package 纯字符串;

import java.util.Stack;

public class No394字符串解码 {

    /**
     * 给定一个经过编码的字符串，返回它解码后的字符串。
     * 编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
     * 你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
     * 此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
     *
     * 示例 1：
     * 输入：s = "3[a]2[bc]"
     * 输出："aaabcbc"
     * 示例 2：
     * 输入：s = "3[a2[c]]"
     * 输出："accaccacc"
     * 示例 3：
     * 输入：s = "2[abc]3[cd]ef"
     * 输出："abcabccdcdcdef"
     * 示例 4：
     * 输入：s = "abc3[cd]xyz"
     * 输出："abccdcdcdxyz"
     */

    public String decodeString(String s) {

        char[] arr = s.toCharArray();

        Stack<Character> stack=new Stack<>();
        int index=0;

        while (index<arr.length){

            char c=arr[index];

            if(c==']'){
                //开始出栈,特殊处理

                StringBuilder sb=new StringBuilder();

                while (stack.peek()!='['){
                    sb.append(stack.pop());
                }

                //'['出栈
                stack.pop();
                //栈顶为数字(可能多位)
                StringBuilder numSb=new StringBuilder();
                while (!stack.isEmpty()&&Character.isDigit(stack.peek())){
                    numSb.append(stack.pop());
                }
                int count=Integer.parseInt(numSb.reverse().toString());

                //然后重新放入
                for (int i = 0; i < count; i++) {
                    for (int j = sb.length()-1; j >= 0; j--) {
                        stack.add(sb.charAt(j));
                    }
                }

            }else {

                //直接进栈
                stack.add(c);

            }

            index++;

        }

        StringBuilder result=new StringBuilder();

        while (!stack.isEmpty()){
            result.append(stack.pop());
        }

        return result.reverse().toString();
    }

    public static void main(String[] args) {
        No394字符串解码 n=new No394字符串解码();
        String result = n.decodeString("100[le]");
        System.out.println(result);
    }

}
